#include "common.h"

bool hasPathSum(struct TreeNode* root, int targetSum);
bool hasPathSum2(struct TreeNode* root, int targetSum);

struct TreeNode* createNode(int value){
	struct TreeNode* node = malloc(sizeof(struct TreeNode));
	node->val = value;
	return node;
}

int main()
{
	struct TreeNode* root = createNode(5);
	root->left = createNode(4);
	root->right = createNode(8);
	root->left->left = createNode(11);
	root->left->left->right = createNode(2);
	hasPathSum2(root, 22);
	return 0;
}

bool hasPathSum(struct TreeNode* root, int targetSum)
{
	if (root == NULL)
		return false;

	if (root->left == NULL && root->right == NULL)
		return targetSum == root->val;

	return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
}

struct LinkedTreeNode {
	struct TreeNode* node;
	struct LinkedTreeNode* pre;
};

bool hasPathSum2(struct TreeNode* root, int targetSum)
{
	if (root == NULL)
		return false;

	struct LinkedTreeNode* pointer = malloc(sizeof(struct LinkedTreeNode));
	pointer->node = root;
	pointer->pre = NULL;

	while (pointer->pre != NULL) {
		struct TreeNode* curNode = pointer->node;
		pointer = pointer->pre;

		if (targetSum == curNode->val && curNode->left == NULL && curNode->right == NULL)
			return true;

		if (curNode->left != NULL) {
			struct LinkedTreeNode* newNode = malloc(sizeof(struct LinkedTreeNode));
			curNode->left->val = curNode->val + curNode->left->val;
			newNode->node = curNode->left;
			newNode->pre = pointer;
			pointer = newNode;
		}

		if (curNode->right != NULL) {
			struct LinkedTreeNode* newNode = malloc(sizeof(struct LinkedTreeNode));
			curNode->right->val = curNode->val + curNode->right->val;
			newNode->node = curNode->right;
			newNode->pre = pointer;
			pointer = newNode;
		}
	}

	return false;
}
